package sort;

import java.util.Arrays;

/**
 * 插入排序
 * 把所有元素分为已排序和未排序两组
 * 找到未排序中的第一个元素，向已排序的组中进行插入
 * 倒序遍历已排序的元素，遇到大的数则位置交换，直到找到一个比待插入的元素小的。
 */
public class Insert {

    public static void main(String[] args) {
        Integer[] arr = {1,3,4,2,6,5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(Comparable[] a){
        for(int i=1;i<a.length;i++){
            for(int j=i;j>0;j--){
                if(greater(a[j-1],a[j])){
                    exch(a,j-1,j);
                }else{
                    break;
                }
            }
        }
    }

    public static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;  //v>=w，返回true；v<w返回false
    }

    public static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
